package tree;

/**
 * Created with IntelliJ IDEA.
 * Description: 98. 验证二叉搜索树
 * User: Li_yizYa
 * Date: 2025/6/5
 * Time: 22:24
 */
public class Solution28 {

    /**
     * 方法2（递归）
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        return validBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean validBST(TreeNode root, long lower, long upper) {
        if (root == null) {
            return true;
        }
        if (root.val <= lower || root.val >= upper) {
            return false;
        }
        return validBST(root.left, lower, root.val) && validBST(root.right, root.val, upper);
    }

    /**
     * 方法1（递归）
     */
    TreeNode max;
    public boolean isValidBST1(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 左
        boolean left = isValidBST1(root.left);
        if (!left) {
            return false;
        }
        // 中
        if (max != null && root.val <= max.val) {
            return false;
        }
        max = root;

        // 右
        boolean right = isValidBST1(root.right);
        return right;
    }
}
